#pragma once
#include"vector_index.h"
#include<string>
#include<algorithm>
#include<vector>


template<class iterator>
int maxPrefix(iterator first_begin, iterator first_end, iterator second_begin, iterator second_end){
	int maxPrefixLength = 0;
	while (first_begin != first_end && second_begin != second_end && *first_begin == *second_begin) {
		++first_begin;
		++second_begin;
		++maxPrefixLength;
	}
	return maxPrefixLength;
}

template<class iterator>
void lcsStep(SignedArray<int>& max_result, int distance,
	iterator first_begin, iterator first_end,
	iterator second_begin, iterator second_end){
	int first_size = first_end - first_begin;
	int second_size = second_end - second_begin;
	for (int diagonal_number = -distance; diagonal_number <= distance; diagonal_number += 2){
		int current_x;
		if (diagonal_number == -distance){
			current_x = max_result[diagonal_number + 1];
		}
		else if (diagonal_number == distance){
			current_x = max_result[diagonal_number - 1] +1;
		}
		else{
			current_x = max(max_result[diagonal_number - 1] + 1, max_result[diagonal_number + 1]);
		}
		int current_y = current_x - diagonal_number;
		if (current_x <= first_size && current_y <= second_size){
			size_t max_current_prefix = maxPrefix(first_begin + current_x, first_end, second_begin + current_y, second_end);
			current_x += max_current_prefix;
			current_y += max_current_prefix;
		}
		max_result[diagonal_number] = current_x;
	}
}
template<class iterator>
int get_edit_distance(iterator first_begin, iterator first_end, iterator second_begin, iterator second_end){
	int first_size = first_end - first_begin;
	int second_size = second_end - second_begin;
	SignedArray<int> max_result(2 * (first_size)+2 * (second_size)+1,
		first_size + second_size);
	max_result[0] = maxPrefix(first_begin, first_end, second_begin, second_end);
	int shift = first_size - second_size;
	if (max_result[shift] >= first_size)
		return 0;
	
	for (int distance = 1; distance <= first_size + second_size; ++distance){
		lcsStep(max_result, distance, first_begin, first_end, second_begin, second_end);
		if (max_result[shift] >= first_size){
			return distance;
		} 
	}
}
